package org.example;

public class MergeSort implements Sort {

    int[] tmp = new int[100000];

    @Override
    public void MySort(int[] num) {
        merge_sort(num,0,num.length - 1);
    }

    void merge_sort(int q[], int l, int r)
    {
        if (l >= r) return;

        int mid = l + r >> 1;
        merge_sort(q, l, mid);
        merge_sort(q, mid + 1, r);

        int k = 0, i = l, j = mid + 1;
        while (i <= mid && j <= r)
            if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
            else tmp[k ++ ] = q[j ++ ];

        while (i <= mid) tmp[k ++ ] = q[i ++ ];
        while (j <= r) tmp[k ++ ] = q[j ++ ];

        for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
    }
}
